/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/convert-expression-to-reverse-polish-notation
   @Language: C++
   @Datetime: 16-02-09 08:54
   */

// Method 1
class Solution {
	vector<string> core(vector<string> &exps, int &i){
		vector<string> res;
		stack<string> opt;
		for(; i<exps.size(); ++i){
			if(isdigit(exps[i][0]) || exps[i].length()>1){
				res.push_back(exps[i]);
				continue;
			}
			if(exps[i][0]=='+' || exps[i][0]=='-'){
				for(; opt.size(); opt.pop())
					res.push_back(opt.top());
				opt.push(exps[i]);
			}
			else if(exps[i][0]=='*' || exps[i][0]=='/'){
				if(opt.size() && (opt.top()[0]=='*'||opt.top()[0]=='/')){
					res.push_back(opt.top());
					opt.pop();
				}
				opt.push(exps[i]);
			}
			else if(exps[i][0]=='('){
				const auto tmp=core(exps, ++i);
				res.insert(res.end(),tmp.begin(),tmp.end());
			}
			else if(exps[i][0]==')') break;
		}
		for(; opt.size(); opt.pop())
			res.push_back(opt.top());
		return res;
	}
public:
	/**
	 * @param expression: A string array
	 * @return: The Reverse Polish notation of this expression
	 */
	vector<string> convertToRPN(vector<string> &expression) {
		// write your code here
		int i=0;
		return core(expression,i);
	}
};

// Method 2, using increasing stack to convert RPN
class Solution {
	typedef pair<string,int> Node;
	void add(stack<Node> &s, vector<string> &res, Node cur){
		for(; s.size() && s.top().second>=cur.second; s.pop())
			res.push_back(s.top().first);
		s.push(cur);
	}
public:
	/**
	 * @param expression: A string array
	 * @return: The Reverse Polish notation of this expression
	 */
	vector<string> convertToRPN(vector<string> &exps) {
		// write your code here
		stack<Node> s;
		vector<string> res;
		for(int weight=0, i=0; i<exps.size(); ++i){
			if(isdigit(exps[i][0]) || exps[i].length()>1)
				add(s,res,{exps[i],3+weight});
			else if(exps[i][0]=='+' || exps[i][0]=='-')
				add(s,res,{exps[i],1+weight});
			else if(exps[i][0]=='*' || exps[i][0]=='/')
				add(s,res,{exps[i],2+weight});
			else if(exps[i][0]=='(') weight+=2;
			else if(exps[i][0]==')') weight-=2;
		}
		add(s,res,{"",0});
		return res;
	}
};
